package com.lfg.leetcode.leetcode100;


import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class No187findRepeatedDnaSequences {

    public static void main(String[] args) {
        List<String> ret = findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
        System.out.println(ret);
    }


    public static List<String> findRepeatedDnaSequences(String s) {
        List<String> ret = new ArrayList<>();
        int mask = 0x7FFFFFF;
        int cur = 0;
        int i = 0;
        int length = s.length();
        for (; i < 9 && i < length; i++) {
            cur = (cur << 3) | (s.charAt(i) & 0x7);
        }

        Set<Integer> data = new HashSet<>(length);
        Set<String> retSet = new HashSet<>(length);
        for (; i < length; i++) {
            cur = ((cur & mask) << 3) | (s.charAt(i) & 0x7);
            if (!data.add(cur)) {
                retSet.add(s.substring(i - 9, i + 1));
            }
        }
        return new ArrayList<>(retSet);
    }

    public static List<String> findRepeatedDnaSequences2(String s) {
        List<String> ret = new ArrayList<>();
        if (null == s) {
            return ret;
        }
        Set<String> data = new HashSet<>();
        Set<String> retSet = new HashSet<>();
        int length = s.length();
        int endIndex = length - 9;
        for (int i = 0; i < endIndex; i++) {
            String key = s.substring(i, i + 10);
            if (!data.add(key)) {
                retSet.add(key);
            }
        }
        return new ArrayList<>(retSet);
    }
}
